package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No51 {
    public static void main(String[] args) {
        solveNQueens(4);
    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[][] value= new boolean[n][n];
        backTrack(value,result,n,0,new ArrayList<>());
//        for (List<String> list : result) {
//            for (String s : list) {
//                System.out.println(s);
//            }
//            System.out.println("---------------");
//        }
//        for (boolean[] booleans : value) {
//            for (boolean aBoolean : booleans) {
//                System.out.print(aBoolean+ " ");
//            }
//            System.out.println();
//        }
        //System.out.println(result);
//        System.out.println( result);
        return result;
    }

    public static void backTrack(boolean[][] value,List<List<String>> result,int n,int index,List<String> list){
        if(index==n){
            result.add(new ArrayList<>(list));
//            for (String s : list) {
//                System.out.println(s);
//            }
//            for (boolean[] booleans : value) {
//                for (boolean aBoolean : booleans) {
//                    System.out.print(aBoolean+" ");
//                }
//                System.out.println();
//            }
            return;
        }
        char[] chars = new char[n];
        for (int i = 0; i < n; i++) {
            chars[i]='.';
        }
        for (int i = 0; i < n; i++) {
            if(!value[index][i]){
                chars[i]='Q';
                list.add(new String(chars));
                backTrack(getvalue(value,index,i),result,n,index+1,list);
                list.remove(list.size()-1);
                chars[i]='.';
            }
        }
    }

    private static boolean[][] deepCopy(boolean[][] original) {
        boolean[][] copy = new boolean[original.length][];
        for (int i = 0; i < original.length; i++) {
            copy[i] = Arrays.copyOf(original[i], original[i].length);
        }
        return copy;
    }

    public static boolean[][] getvalue(boolean[][] value,int m,int n){
//        System.out.println("当前");
//        for (boolean[] booleans : value) {
//            for (boolean aBoolean : booleans) {
//                System.out.print(aBoolean+" ");
//            }
//            System.out.println();
//        }
//        System.out.println("------------");
        boolean[][] newValue = deepCopy(value);
        for (int i = 0; i < newValue[0].length; i++) {
            newValue[m][i]=true;

        }
        for (int i = 0; i < newValue.length; i++) {
            newValue[i][n]=true;
        }
        int[][] directions = {{1,1},{-1,1},{-1,-1},{1,-1}};
        for (int i = 0; i < directions.length; i++) {
            int newm = m + directions[i][0];  // 直接从下一个位置开始
            int newn = n + directions[i][1];
            while(newm >= 0 && newm <newValue.length &&
                    newn >= 0 && newn <newValue[0].length) {
                newValue[newm][newn] = true;
                newm += directions[i][0];
                newn += directions[i][1];
            }
        }
//        System.out.println("m = " + m);
//        System.out.println("n = " + n);
//        for (boolean[] booleans : newValue) {
//            for (boolean aBoolean : booleans) {
//                System.out.print(aBoolean+" ");
//            }
//            System.out.println();
//        }
//        System.out.println("--------------");
        return newValue;
    }

}
